package com.vint.leetcode;

import com.vint.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Copyright (C) 2017, Xiaomi Inc. All rights reserved.
 * Created by vint @ 2017/10/21.
 * in leetcode
 */
public class Leetcode623 {

    public TreeNode addOneRow(TreeNode root, int v, int d) {
        TreeNode ret = null;
        if( 1 == d){
            ret = new TreeNode(v);
            ret.left = root;
            return ret;
        }
        int depth = 1;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int size =queue.size();
        while (!queue.isEmpty()){
            if(depth==d-1)
                break;
            for(int i = 0; i < size; i++){
                TreeNode treeNode = queue.poll();
                if(treeNode.left != null){
                    queue.offer(treeNode.left);
                }
                if(treeNode.right!= null){
                    queue.offer(treeNode.right);
                }
            }
            size = queue.size();
            depth ++;
        }
        if(depth==d-1){
            while (!queue.isEmpty()){
                TreeNode treeNode = queue.poll();
                TreeNode left = new TreeNode(v);
                TreeNode right = new TreeNode(v);
                left.left = (null==treeNode.left)?null:treeNode.left;
                right.right= (null==treeNode.right)?null:treeNode.right;
                treeNode.left = left;
                treeNode.right = right;
            }
            return root;
        }
        //这种情况就是d大于树的深度，返回为空
        return null;
    }
    public static void main(String[] args) {
        TreeNode root = TreeNode.mockSpecific1();
        Leetcode623 leetcode623 = new Leetcode623();
        TreeNode ret = leetcode623.addOneRow(root, 5,2);
        System.out.println("success!");
    }
}
